package leetcode每日一题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1. 问题描述
 *      给你一个points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。
 *      连接点[xi, yi] 和点[xj, yj]的费用为它们之间的 曼哈顿距离：|xi - xj| + |yi - yj|，其中|val|表示val的绝对值。
 *      请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有一条简单路径时，才认为所有点都已连接。
 *
 * 2. 算法分析
 *      采用kruskal算法实现最小生成树的构造，由于kruskal算法是本质上每次选取当前最小权值的边添加到树中
 *      (贪心),但是此时的贪心是有限制的，即添加到树中不能出现环，所以我们采用并查集来实现判断是否成环，
 *      整体的思路如下：
 *          1. 将points数组转化为图的压缩数组形式{{x,y,weight(x,y)}} x，y均为points数组中的索引，
 *             weight(x,y)为索引对应顶点的曼哈顿距离
 *          2. 实现一个并查集
 *          3. 上述都是辅助，下面为正式的代码：
 *              实际上我们只需要考虑什么情况下会成环?即如果当前边的两个顶点的父节点相同
 *              {x,y,weight} x ---> z y ---> z 显然如果将边{x,y} 添加之后就会成环
 *          4. 根据最小生成树的定义可知，n个顶点的带权完全连通图的最小生成树有n-1条边，所以
 *             可以设置一个变量来记录当前树中的边数，由此来作为程序结束的标志
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 连接所有点的最小费用 {
    class UnionFind {
        int[] root;
        int[] rank;
        int pointCounts;

        public UnionFind(int pointCounts) {
            this.pointCounts = pointCounts;
            this.root = new int[pointCounts];
            this.rank = new int[pointCounts];
            for (int i = 0; i < pointCounts; i++) {
                this.root[i] = i;
                this.rank[i] = 1;
            }
        }

        public int find(int x) {
            if (root[x] == x) {
                return x;
            }
            return find(root[x]);
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                } else if (rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                } else if (rank[rootX] == rank[rootY]) {
                    root[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }

        public int minCostConnectPoints(int[][] points) {
            int[][] graph = generateGraph(points); // 生成压缩数组构成的完全连通图
            Arrays.sort(graph, (a, b) -> a[2] - b[2]); // 按照权值从小到大排序
            int pointCounts = points.length; // 获取顶点总数
            UnionFind uf = new UnionFind(pointCounts); // 创建并查集
            int minCost = 0; // 记录总体的最小费用
            int edgeCounts = 0; // 记录当前树中的边数
            // 由最小生成树的定义，我们知道n个顶点的完全连通图的最小生成树的边数为n-1
            // 所以程序结束的标志位 edgeCounts = pointCounts - 1
            for (int[] edge : graph) { // 扫描所有边
                // 判断将当前边加入到树中是否成环，如果成环舍弃当前变，如果不成环，将当前边添加到树中
                // 如何判断成环呢?
                // 如果当前边的两个顶点对应的父节点相同，则将此边添加进行之后就会成环
                // 所以我们只需要调用find方法获取两个顶点的父节点即可
                int vertex1 = edge[0]; // 获取第一个顶点的索引
                int vertex2 = edge[1]; // 获取第二个顶点的索引
                int root1 = uf.find(vertex1);
                int root2 = uf.find(vertex2);
                if (root1 != root2) {
                    // 此时不成环
                    minCost += edge[2];
                    edgeCounts++;
                    uf.union(vertex1, vertex2);
                }
                if (edgeCounts == pointCounts - 1) {
                    break;
                }
            }
            return minCost;
        }

        // 生成完全带权连通图 {x,y,weight(x,y)}
        // x,y均为points数组中的顶点对应的索引，weight(x,y)为索引对应的顶点的曼哈顿距离
        public int[][] generateGraph(int[][] points) {
            int[][] graph = new int[(points.length - 1) * points.length / 2][3];
            int index = 0;
            for (int i = 0; i < points.length; i++) {
                for (int j = i + 1; j < points.length; j++) {
                    graph[index] = new int[]{i, j, getVal(points[i], points[j])};
                    index++;
                }
            }
            return graph;
        }

        // 计算两个点之间的曼哈顿距离
        public int getVal(int[] point1, int[] point2) {
            return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
        }
    }
}
